package graph.algo;

import graph.model.Graph;

import java.util.Stack;

public class DFS {

	private Graph graph;

	public DFS(Graph graph) {
		this.graph = graph;
	}

	public void dfs() {
		Stack<Integer> stack = new Stack<Integer>();

		graph.getVertices()[0].setVisited(true); // start with the first
													// vertex
		graph.displayVertex(0); // display it
		stack.push(0); // push onto the stack

		while (!stack.isEmpty()) {
			// Get adjacent vertex
			int adjVertex = graph.getAdjUnVisitedVertex(stack.peek());

			if (adjVertex == -1) {
				stack.pop();
			} else {
				graph.displayVertex(adjVertex); // 1. Display the vertex
				stack.push(adjVertex); // 2. Push it onto the stack, so that it
										// is remembered
				graph.getVertices()[adjVertex].setVisited(true); // Mark it,
																	// so that
																	// it is not
																	// visited
																	// again.
			}
		}

		// Once done with searching, reset the visited status of all vertex.
		//graph.resetVisited();
	}

	public static void main(String[] args) {

		Graph graph = new Graph(5, 4, false, false);
		graph.addVertex(0, 'A');
		graph.addVertex(1, 'B');
		graph.addVertex(2, 'C');
		graph.addVertex(3, 'D');
		graph.addVertex(4,  'E');

		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(0, 3);
		graph.addEdge(3, 4);

		System.out.println("Visits:");
		DFS dfs = new DFS(graph);
		dfs.dfs();
		System.out.println();
	}
}
